/*
 * L.MarkerClusterGroup extends L.FeatureGroup by clustering the markers contained within
 */

export var MarkerClusterGroup = L.MarkerClusterGroup = L.FeatureGroup.extend({

    options: {
        maxClusterRadius: 80, //A cluster will cover at most this many pixels from its center
        iconCreateFunction: null,
        clusterPane: L.Marker.prototype.options.pane,

        spiderfyOnMaxZoom: true,
        showCoverageOnHover: true,
        zoomToBoundsOnClick: true,
        singleMarkerMode: false,

        disableClusteringAtZoom: null,

        // Setting this to false prevents the removal of any clusters outside of the viewpoint, which
        // is the default behaviour for performance reasons.
        removeOutsideVisibleBounds: true,

        // Set to false to disable all animations (zoom and spiderfy).
        // If false, option animateAddingMarkers below has no effect.
        // If L.DomUtil.TRANSITION is falsy, this option has no effect.
        animate: true,

        //Whether to animate adding markers after adding the MarkerClusterGroup to the map
        // If you are adding individual markers set to true, if adding bulk markers leave false for massive performance gains.
        animateAddingMarkers: false,

        // Make it possible to provide custom function to calculate spiderfy shape positions
        spiderfyShapePositions: null,

        //Increase to increase the distance away that spiderfied markers appear from the center
        spiderfyDistanceMultiplier: 1,

        // Make it possible to specify a polyline options on a spider leg
        spiderLegPolylineOptions: {weight: 1.5, color: '#222', opacity: 0.5},

        // When bulk adding layers, adds markers in chunks. Means addLayers may not add all the layers in the call, others will be loaded during setTimeouts
        chunkedLoading: false,
        chunkInterval: 200, // process markers for a maximum of ~ n milliseconds (then trigger the chunkProgress callback)
        chunkDelay: 50, // at the end of each interval, give n milliseconds back to system/browser
        chunkProgress: null, // progress callback: function(processed, total, elapsed) (e.g. for a progress indicator)

        //Options to pass to the L.Polygon constructor
        polygonOptions: {}
    },

    initialize: function (options) {
        L.Util.setOptions(this, options);
        if (!this.options.iconCreateFunction) {
            this.options.iconCreateFunction = this._defaultIconCreateFunction;
        }

        this._featureGroup = L.featureGroup();
        this._featureGroup.addEventParent(this);

        this._nonPointGroup = L.featureGroup();
        this._nonPointGroup.addEventParent(this);

        this._inZoomAnimation = 0;
        this._needsClustering = [];
        this._needsRemoving = []; //Markers removed while we aren't on the map need to be kept track of
        //The bounds of the currently shown area (from _getExpandedVisibleBounds) Updated on zoom/move
        this._currentShownBounds = null;

        this._queue = [];

        this._childMarkerEventHandlers = {
            'dragstart': this._childMarkerDragStart,
            'move': this._childMarkerMoved,
            'dragend': this._childMarkerDragEnd,
        };

        // Hook the appropriate animation methods.
        var animate = L.DomUtil.TRANSITION && this.options.animate;
        L.extend(this, animate ? this._withAnimation : this._noAnimation);
        // Remember which MarkerCluster class to instantiate (animated or not).
        this._markerCluster = animate ? L.MarkerCluster : L.MarkerClusterNonAnimated;
    },

    addLayer: function (layer) {

        if (layer instanceof L.LayerGroup) {
            return this.addLayers([layer]);
        }

        //Don't cluster non point data
        if (!layer.getLatLng) {
            this._nonPointGroup.addLayer(layer);
            this.fire('layeradd', {layer: layer});
            return this;
        }

        if (!this._map) {
            this._needsClustering.push(layer);
            this.fire('layeradd', {layer: layer});
            return this;
        }

        if (this.hasLayer(layer)) {
            return this;
        }


        //If we have already clustered we'll need to add this one to a cluster

        if (this._unspiderfy) {
            this._unspiderfy();
        }

        this._addLayer(layer, this._maxZoom);
        this.fire('layeradd', {layer: layer});

        // Refresh bounds and weighted positions.
        this._topClusterLevel._recalculateBounds();

        this._refreshClustersIcons();

        //Work out what is visible
        var visibleLayer = layer,
            currentZoom = this._zoom;
        if (layer.__parent) {
            while (visibleLayer.__parent._zoom >= currentZoom) {
                visibleLayer = visibleLayer.__parent;
            }
        }

        if (this._currentShownBounds.contains(visibleLayer.getLatLng())) {
            if (this.options.animateAddingMarkers) {
                this._animationAddLayer(layer, visibleLayer);
            } else {
                this._animationAddLayerNonAnimated(layer, visibleLayer);
            }
        }
        return this;
    },

    removeLayer: function (layer) {

        if (layer instanceof L.LayerGroup) {
            return this.removeLayers([layer]);
        }

        //Non point layers
        if (!layer.getLatLng) {
            this._nonPointGroup.removeLayer(layer);
            this.fire('layerremove', {layer: layer});
            return this;
        }

        if (!this._map) {
            if (!this._arraySplice(this._needsClustering, layer) && this.hasLayer(layer)) {
                this._needsRemoving.push({layer: layer, latlng: layer._latlng});
            }
            this.fire('layerremove', {layer: layer});
            return this;
        }

        if (!layer.__parent) {
            return this;
        }

        if (this._unspiderfy) {
            this._unspiderfy();
            this._unspiderfyLayer(layer);
        }

        //Remove the marker from clusters
        this._removeLayer(layer, true);
        this.fire('layerremove', {layer: layer});

        // Refresh bounds and weighted positions.
        this._topClusterLevel._recalculateBounds();

        this._refreshClustersIcons();

        layer.off(this._childMarkerEventHandlers, this);

        if (this._featureGroup.hasLayer(layer)) {
            this._featureGroup.removeLayer(layer);
            if (layer.clusterShow) {
                layer.clusterShow();
            }
        }

        return this;
    },

    //Takes an array of markers and adds them in bulk
    addLayers: function (layersArray, skipLayerAddEvent) {
        if (!L.Util.isArray(layersArray)) {
            return this.addLayer(layersArray);
        }

        var fg = this._featureGroup,
            npg = this._nonPointGroup,
            chunked = this.options.chunkedLoading,
            chunkInterval = this.options.chunkInterval,
            chunkProgress = this.options.chunkProgress,
            l = layersArray.length,
            offset = 0,
            originalArray = true,
            m;

        if (this._map) {
            var started = (new Date()).getTime();
            var process = L.bind(function () {
                var start = (new Date()).getTime();

                // Make sure to unspiderfy before starting to add some layers
                if (this._map && this._unspiderfy) {
                    this._unspiderfy();
                }

                for (; offset < l; offset++) {
                    if (chunked && offset % 200 === 0) {
                        // every couple hundred markers, instrument the time elapsed since processing started:
                        var elapsed = (new Date()).getTime() - start;
                        if (elapsed > chunkInterval) {
                            break; // been working too hard, time to take a break :-)
                        }
                    }

                    m = layersArray[offset];

                    // Group of layers, append children to layersArray and skip.
                    // Side effects:
                    // - Total increases, so chunkProgress ratio jumps backward.
                    // - Groups are not included in this group, only their non-group child layers (hasLayer).
                    // Changing array length while looping does not affect performance in current browsers:
                    // http://jsperf.com/for-loop-changing-length/6
                    if (m instanceof L.LayerGroup) {
                        if (originalArray) {
                            layersArray = layersArray.slice();
                            originalArray = false;
                        }
                        this._extractNonGroupLayers(m, layersArray);
                        l = layersArray.length;
                        continue;
                    }

                    //Not point data, can't be clustered
                    if (!m.getLatLng) {
                        npg.addLayer(m);
                        if (!skipLayerAddEvent) {
                            this.fire('layeradd', {layer: m});
                        }
                        continue;
                    }

                    if (this.hasLayer(m)) {
                        continue;
                    }

                    this._addLayer(m, this._maxZoom);
                    if (!skipLayerAddEvent) {
                        this.fire('layeradd', {layer: m});
                    }

                    //If we just made a cluster of size 2 then we need to remove the other marker from the map (if it is) or we never will
                    if (m.__parent) {
                        if (m.__parent.getChildCount() === 2) {
                            var markers = m.__parent.getAllChildMarkers(),
                                otherMarker = markers[0] === m ? markers[1] : markers[0];
                            fg.removeLayer(otherMarker);
                        }
                    }
                }

                if (chunkProgress) {
                    // report progress and time elapsed:
                    chunkProgress(offset, l, (new Date()).getTime() - started);
                }

                // Completed processing all markers.
                if (offset === l) {

                    // Refresh bounds and weighted positions.
                    this._topClusterLevel._recalculateBounds();

                    this._refreshClustersIcons();

                    this._topClusterLevel._recursivelyAddChildrenToMap(null, this._zoom, this._currentShownBounds);
                } else {
                    setTimeout(process, this.options.chunkDelay);
                }
            }, this);

            process();
        } else {
            var needsClustering = this._needsClustering;

            for (; offset < l; offset++) {
                m = layersArray[offset];

                // Group of layers, append children to layersArray and skip.
                if (m instanceof L.LayerGroup) {
                    if (originalArray) {
                        layersArray = layersArray.slice();
                        originalArray = false;
                    }
                    this._extractNonGroupLayers(m, layersArray);
                    l = layersArray.length;
                    continue;
                }

                //Not point data, can't be clustered
                if (!m.getLatLng) {
                    npg.addLayer(m);
                    continue;
                }

                if (this.hasLayer(m)) {
                    continue;
                }

                needsClustering.push(m);
            }
        }
        return this;
    },

    //Takes an array of markers and removes them in bulk
    removeLayers: function (layersArray) {
        var i, m,
            l = layersArray.length,
            fg = this._featureGroup,
            npg = this._nonPointGroup,
            originalArray = true;

        if (!this._map) {
            for (i = 0; i < l; i++) {
                m = layersArray[i];

                // Group of layers, append children to layersArray and skip.
                if (m instanceof L.LayerGroup) {
                    if (originalArray) {
                        layersArray = layersArray.slice();
                        originalArray = false;
                    }
                    this._extractNonGroupLayers(m, layersArray);
                    l = layersArray.length;
                    continue;
                }

                this._arraySplice(this._needsClustering, m);
                npg.removeLayer(m);
                if (this.hasLayer(m)) {
                    this._needsRemoving.push({layer: m, latlng: m._latlng});
                }
                this.fire('layerremove', {layer: m});
            }
            return this;
        }

        if (this._unspiderfy) {
            this._unspiderfy();

            // Work on a copy of the array, so that next loop is not affected.
            var layersArray2 = layersArray.slice(),
                l2 = l;
            for (i = 0; i < l2; i++) {
                m = layersArray2[i];

                // Group of layers, append children to layersArray and skip.
                if (m instanceof L.LayerGroup) {
                    this._extractNonGroupLayers(m, layersArray2);
                    l2 = layersArray2.length;
                    continue;
                }

                this._unspiderfyLayer(m);
            }
        }

        for (i = 0; i < l; i++) {
            m = layersArray[i];

            // Group of layers, append children to layersArray and skip.
            if (m instanceof L.LayerGroup) {
                if (originalArray) {
                    layersArray = layersArray.slice();
                    originalArray = false;
                }
                this._extractNonGroupLayers(m, layersArray);
                l = layersArray.length;
                continue;
            }

            if (!m.__parent) {
                npg.removeLayer(m);
                this.fire('layerremove', {layer: m});
                continue;
            }

            this._removeLayer(m, true, true);
            this.fire('layerremove', {layer: m});

            if (fg.hasLayer(m)) {
                fg.removeLayer(m);
                if (m.clusterShow) {
                    m.clusterShow();
                }
            }
        }

        // Refresh bounds and weighted positions.
        this._topClusterLevel._recalculateBounds();

        this._refreshClustersIcons();

        //Fix up the clusters and markers on the map
        this._topClusterLevel._recursivelyAddChildrenToMap(null, this._zoom, this._currentShownBounds);

        return this;
    },

    //Removes all layers from the MarkerClusterGroup
    clearLayers: function () {
        //Need our own special implementation as the LayerGroup one doesn't work for us

        //If we aren't on the map (yet), blow away the markers we know of
        if (!this._map) {
            this._needsClustering = [];
            this._needsRemoving = [];
            delete this._gridClusters;
            delete this._gridUnclustered;
        }

        if (this._noanimationUnspiderfy) {
            this._noanimationUnspiderfy();
        }

        //Remove all the visible layers
        this._featureGroup.clearLayers();
        this._nonPointGroup.clearLayers();

        this.eachLayer(function (marker) {
            marker.off(this._childMarkerEventHandlers, this);
            delete marker.__parent;
        }, this);

        if (this._map) {
            //Reset _topClusterLevel and the DistanceGrids
            this._generateInitialClusters();
        }

        return this;
    },

    //Override FeatureGroup.getBounds as it doesn't work
    getBounds: function () {
        var bounds = new L.LatLngBounds();

        if (this._topClusterLevel) {
            bounds.extend(this._topClusterLevel._bounds);
        }

        for (var i = this._needsClustering.length - 1; i >= 0; i--) {
            bounds.extend(this._needsClustering[i].getLatLng());
        }

        bounds.extend(this._nonPointGroup.getBounds());

        return bounds;
    },

    //Overrides LayerGroup.eachLayer
    eachLayer: function (method, context) {
        var markers = this._needsClustering.slice(),
            needsRemoving = this._needsRemoving,
            thisNeedsRemoving, i, j;

        if (this._topClusterLevel) {
            this._topClusterLevel.getAllChildMarkers(markers);
        }

        for (i = markers.length - 1; i >= 0; i--) {
            thisNeedsRemoving = true;

            for (j = needsRemoving.length - 1; j >= 0; j--) {
                if (needsRemoving[j].layer === markers[i]) {
                    thisNeedsRemoving = false;
                    break;
                }
            }

            if (thisNeedsRemoving) {
                method.call(context, markers[i]);
            }
        }

        this._nonPointGroup.eachLayer(method, context);
    },

    //Overrides LayerGroup.getLayers
    getLayers: function () {
        var layers = [];
        this.eachLayer(function (l) {
            layers.push(l);
        });
        return layers;
    },

    //Overrides LayerGroup.getLayer, WARNING: Really bad performance
    getLayer: function (id) {
        var result = null;

        id = parseInt(id, 10);

        this.eachLayer(function (l) {
            if (L.stamp(l) === id) {
                result = l;
            }
        });

        return result;
    },

    //Returns true if the given layer is in this MarkerClusterGroup
    hasLayer: function (layer) {
        if (!layer) {
            return false;
        }

        var i, anArray = this._needsClustering;

        for (i = anArray.length - 1; i >= 0; i--) {
            if (anArray[i] === layer) {
                return true;
            }
        }

        anArray = this._needsRemoving;
        for (i = anArray.length - 1; i >= 0; i--) {
            if (anArray[i].layer === layer) {
                return false;
            }
        }

        return !!(layer.__parent && layer.__parent._group === this) || this._nonPointGroup.hasLayer(layer);
    },

    //Zoom down to show the given layer (spiderfying if necessary) then calls the callback
    zoomToShowLayer: function (layer, callback) {

        var map = this._map;

        if (typeof callback !== 'function') {
            callback = function () {
            };
        }

        var showMarker = function () {
            // Assumes that map.hasLayer checks for direct appearance on map, not recursively calling
            // hasLayer on Layer Groups that are on map (typically not calling this MarkerClusterGroup.hasLayer, which would always return true)
            if ((map.hasLayer(layer) || map.hasLayer(layer.__parent)) && !this._inZoomAnimation) {
                this._map.off('moveend', showMarker, this);
                this.off('animationend', showMarker, this);

                if (map.hasLayer(layer)) {
                    callback();
                } else if (layer.__parent._icon) {
                    this.once('spiderfied', callback, this);
                    layer.__parent.spiderfy();
                }
            }
        };

        if (layer._icon && this._map.getBounds().contains(layer.getLatLng())) {
            //Layer is visible ond on screen, immediate return
            callback();
        } else if (layer.__parent._zoom < Math.round(this._map._zoom)) {
            //Layer should be visible at this zoom level. It must not be on screen so just pan over to it
            this._map.on('moveend', showMarker, this);
            this._map.panTo(layer.getLatLng());
        } else {
            this._map.on('moveend', showMarker, this);
            this.on('animationend', showMarker, this);
            layer.__parent.zoomToBounds();
        }
    },

    //Overrides FeatureGroup.onAdd
    onAdd: function (map) {
        this._map = map;
        var i, l, layer;

        if (!isFinite(this._map.getMaxZoom())) {
            throw "Map has no maxZoom specified";
        }

        this._featureGroup.addTo(map);
        this._nonPointGroup.addTo(map);

        if (!this._gridClusters) {
            this._generateInitialClusters();
        }

        this._maxLat = map.options.crs.projection.MAX_LATITUDE;

        //Restore all the positions as they are in the MCG before removing them
        for (i = 0, l = this._needsRemoving.length; i < l; i++) {
            layer = this._needsRemoving[i];
            layer.newlatlng = layer.layer._latlng;
            layer.layer._latlng = layer.latlng;
        }
        //Remove them, then restore their new positions
        for (i = 0, l = this._needsRemoving.length; i < l; i++) {
            layer = this._needsRemoving[i];
            this._removeLayer(layer.layer, true);
            layer.layer._latlng = layer.newlatlng;
        }
        this._needsRemoving = [];

        //Remember the current zoom level and bounds
        this._zoom = Math.round(this._map._zoom);
        this._currentShownBounds = this._getExpandedVisibleBounds();

        this._map.on('zoomend', this._zoomEnd, this);
        this._map.on('moveend', this._moveEnd, this);

        if (this._spiderfierOnAdd) { //TODO FIXME: Not sure how to have spiderfier add something on here nicely
            this._spiderfierOnAdd();
        }

        this._bindEvents();

        //Actually add our markers to the map:
        l = this._needsClustering;
        this._needsClustering = [];
        this.addLayers(l, true);
    },

    //Overrides FeatureGroup.onRemove
    onRemove: function (map) {
        map.off('zoomend', this._zoomEnd, this);
        map.off('moveend', this._moveEnd, this);

        this._unbindEvents();

        //In case we are in a cluster animation
        this._map._mapPane.className = this._map._mapPane.className.replace(' leaflet-cluster-anim', '');

        if (this._spiderfierOnRemove) { //TODO FIXME: Not sure how to have spiderfier add something on here nicely
            this._spiderfierOnRemove();
        }

        delete this._maxLat;

        //Clean up all the layers we added to the map
        this._hideCoverage();
        this._featureGroup.remove();
        this._nonPointGroup.remove();

        this._featureGroup.clearLayers();

        this._map = null;
    },

    getVisibleParent: function (marker) {
        var vMarker = marker;
        while (vMarker && !vMarker._icon) {
            vMarker = vMarker.__parent;
        }
        return vMarker || null;
    },

    //Remove the given object from the given array
    _arraySplice: function (anArray, obj) {
        for (var i = anArray.length - 1; i >= 0; i--) {
            if (anArray[i] === obj) {
                anArray.splice(i, 1);
                return true;
            }
        }
    },

    /**
     * Removes a marker from all _gridUnclustered zoom levels, starting at the supplied zoom.
     * @param marker to be removed from _gridUnclustered.
     * @param z integer bottom start zoom level (included)
     * @private
     */
    _removeFromGridUnclustered: function (marker, z) {
        var map = this._map,
            gridUnclustered = this._gridUnclustered,
            minZoom = Math.floor(this._map.getMinZoom());

        for (; z >= minZoom; z--) {
            if (!gridUnclustered[z].removeObject(marker, map.project(marker.getLatLng(), z))) {
                break;
            }
        }
    },

    _childMarkerDragStart: function (e) {
        e.target.__dragStart = e.target._latlng;
    },

    _childMarkerMoved: function (e) {
        if (!this._ignoreMove && !e.target.__dragStart) {
            var isPopupOpen = e.target._popup && e.target._popup.isOpen();

            this._moveChild(e.target, e.oldLatLng, e.latlng);

            if (isPopupOpen) {
                e.target.openPopup();
            }
        }
    },

    _moveChild: function (layer, from, to) {
        layer._latlng = from;
        this.removeLayer(layer);

        layer._latlng = to;
        this.addLayer(layer);
    },

    _childMarkerDragEnd: function (e) {
        var dragStart = e.target.__dragStart;
        delete e.target.__dragStart;
        if (dragStart) {
            this._moveChild(e.target, dragStart, e.target._latlng);
        }
    },


    //Internal function for removing a marker from everything.
    //dontUpdateMap: set to true if you will handle updating the map manually (for bulk functions)
    _removeLayer: function (marker, removeFromDistanceGrid, dontUpdateMap) {
        var gridClusters = this._gridClusters,
            gridUnclustered = this._gridUnclustered,
            fg = this._featureGroup,
            map = this._map,
            minZoom = Math.floor(this._map.getMinZoom());

        //Remove the marker from distance clusters it might be in
        if (removeFromDistanceGrid) {
            this._removeFromGridUnclustered(marker, this._maxZoom);
        }

        //Work our way up the clusters removing them as we go if required
        var cluster = marker.__parent,
            markers = cluster._markers,
            otherMarker;

        //Remove the marker from the immediate parents marker list
        this._arraySplice(markers, marker);

        while (cluster) {
            cluster._childCount--;
            cluster._boundsNeedUpdate = true;

            if (cluster._zoom < minZoom) {
                //Top level, do nothing
                break;
            } else if (removeFromDistanceGrid && cluster._childCount <= 1) { //Cluster no longer required
                //We need to push the other marker up to the parent
                otherMarker = cluster._markers[0] === marker ? cluster._markers[1] : cluster._markers[0];

                //Update distance grid
                gridClusters[cluster._zoom].removeObject(cluster, map.project(cluster._cLatLng, cluster._zoom));
                gridUnclustered[cluster._zoom].addObject(otherMarker, map.project(otherMarker.getLatLng(), cluster._zoom));

                //Move otherMarker up to parent
                this._arraySplice(cluster.__parent._childClusters, cluster);
                cluster.__parent._markers.push(otherMarker);
                otherMarker.__parent = cluster.__parent;

                if (cluster._icon) {
                    //Cluster is currently on the map, need to put the marker on the map instead
                    fg.removeLayer(cluster);
                    if (!dontUpdateMap) {
                        fg.addLayer(otherMarker);
                    }
                }
            } else {
                cluster._iconNeedsUpdate = true;
            }

            cluster = cluster.__parent;
        }

        delete marker.__parent;
    },

    _isOrIsParent: function (el, oel) {
        while (oel) {
            if (el === oel) {
                return true;
            }
            oel = oel.parentNode;
        }
        return false;
    },

    //Override L.Evented.fire
    fire: function (type, data, propagate) {
        if (data && data.layer instanceof L.MarkerCluster) {
            //Prevent multiple clustermouseover/off events if the icon is made up of stacked divs (Doesn't work in ie <= 8, no relatedTarget)
            if (data.originalEvent && this._isOrIsParent(data.layer._icon, data.originalEvent.relatedTarget)) {
                return;
            }
            type = 'cluster' + type;
        }

        L.FeatureGroup.prototype.fire.call(this, type, data, propagate);
    },

    //Override L.Evented.listens
    listens: function (type, propagate) {
        return L.FeatureGroup.prototype.listens.call(this, type, propagate) || L.FeatureGroup.prototype.listens.call(this, 'cluster' + type, propagate);
    },

    //Default functionality
    _defaultIconCreateFunction: function (cluster) {
        var childCount = cluster.getChildCount();

        var c = ' marker-cluster-';
        if (childCount < 10) {
            c += 'small';
        } else if (childCount < 100) {
            c += 'medium';
        } else {
            c += 'large';
        }

        return new L.DivIcon({
            html: '<div><span>' + childCount + '</span></div>',
            className: 'marker-cluster' + c,
            iconSize: new L.Point(40, 40)
        });
    },

    _bindEvents: function () {
        var map = this._map,
            spiderfyOnMaxZoom = this.options.spiderfyOnMaxZoom,
            showCoverageOnHover = this.options.showCoverageOnHover,
            zoomToBoundsOnClick = this.options.zoomToBoundsOnClick;

        //Zoom on cluster click or spiderfy if we are at the lowest level
        if (spiderfyOnMaxZoom || zoomToBoundsOnClick) {
            this.on('clusterclick clusterkeypress', this._zoomOrSpiderfy, this);
        }

        //Show convex hull (boundary) polygon on mouse over
        if (showCoverageOnHover) {
            this.on('clustermouseover', this._showCoverage, this);
            this.on('clustermouseout', this._hideCoverage, this);
            map.on('zoomend', this._hideCoverage, this);
        }
    },

    _zoomOrSpiderfy: function (e) {
        var cluster = e.layer,
            bottomCluster = cluster;

        if (e.type === 'clusterkeypress' && e.originalEvent && e.originalEvent.keyCode !== 13) {
            return;
        }

        while (bottomCluster._childClusters.length === 1) {
            bottomCluster = bottomCluster._childClusters[0];
        }

        if (bottomCluster._zoom === this._maxZoom &&
            bottomCluster._childCount === cluster._childCount &&
            this.options.spiderfyOnMaxZoom) {

            // All child markers are contained in a single cluster from this._maxZoom to this cluster.
            cluster.spiderfy();
        } else if (this.options.zoomToBoundsOnClick) {
            cluster.zoomToBounds();
        }

        // Focus the map again for keyboard users.
        if (e.originalEvent && e.originalEvent.keyCode === 13) {
            this._map._container.focus();
        }
    },

    _showCoverage: function (e) {
        var map = this._map;
        if (this._inZoomAnimation) {
            return;
        }
        if (this._shownPolygon) {
            map.removeLayer(this._shownPolygon);
        }
        if (e.layer.getChildCount() > 2 && e.layer !== this._spiderfied) {
            this._shownPolygon = new L.Polygon(e.layer.getConvexHull(), this.options.polygonOptions);
            map.addLayer(this._shownPolygon);
        }
    },

    _hideCoverage: function () {
        if (this._shownPolygon) {
            this._map.removeLayer(this._shownPolygon);
            this._shownPolygon = null;
        }
    },

    _unbindEvents: function () {
        var spiderfyOnMaxZoom = this.options.spiderfyOnMaxZoom,
            showCoverageOnHover = this.options.showCoverageOnHover,
            zoomToBoundsOnClick = this.options.zoomToBoundsOnClick,
            map = this._map;

        if (spiderfyOnMaxZoom || zoomToBoundsOnClick) {
            this.off('clusterclick clusterkeypress', this._zoomOrSpiderfy, this);
        }
        if (showCoverageOnHover) {
            this.off('clustermouseover', this._showCoverage, this);
            this.off('clustermouseout', this._hideCoverage, this);
            map.off('zoomend', this._hideCoverage, this);
        }
    },

    _zoomEnd: function () {
        if (!this._map) { //May have been removed from the map by a zoomEnd handler
            return;
        }
        this._mergeSplitClusters();

        this._zoom = Math.round(this._map._zoom);
        this._currentShownBounds = this._getExpandedVisibleBounds();
    },

    _moveEnd: function () {
        if (this._inZoomAnimation) {
            return;
        }

        var newBounds = this._getExpandedVisibleBounds();

        this._topClusterLevel._recursivelyRemoveChildrenFromMap(this._currentShownBounds, Math.floor(this._map.getMinZoom()), this._zoom, newBounds);
        this._topClusterLevel._recursivelyAddChildrenToMap(null, Math.round(this._map._zoom), newBounds);

        this._currentShownBounds = newBounds;
        return;
    },

    _generateInitialClusters: function () {
        var maxZoom = Math.ceil(this._map.getMaxZoom()),
            minZoom = Math.floor(this._map.getMinZoom()),
            radius = this.options.maxClusterRadius,
            radiusFn = radius;

        //If we just set maxClusterRadius to a single number, we need to create
        //a simple function to return that number. Otherwise, we just have to
        //use the function we've passed in.
        if (typeof radius !== "function") {
            radiusFn = function () {
                return radius;
            };
        }

        if (this.options.disableClusteringAtZoom !== null) {
            maxZoom = this.options.disableClusteringAtZoom - 1;
        }
        this._maxZoom = maxZoom;
        this._gridClusters = {};
        this._gridUnclustered = {};

        //Set up DistanceGrids for each zoom
        for (var zoom = maxZoom; zoom >= minZoom; zoom--) {
            this._gridClusters[zoom] = new L.DistanceGrid(radiusFn(zoom));
            this._gridUnclustered[zoom] = new L.DistanceGrid(radiusFn(zoom));
        }

        // Instantiate the appropriate L.MarkerCluster class (animated or not).
        this._topClusterLevel = new this._markerCluster(this, minZoom - 1);
    },

    //Zoom: Zoom to start adding at (Pass this._maxZoom to start at the bottom)
    _addLayer: function (layer, zoom) {
        var gridClusters = this._gridClusters,
            gridUnclustered = this._gridUnclustered,
            minZoom = Math.floor(this._map.getMinZoom()),
            markerPoint, z;

        if (this.options.singleMarkerMode) {
            this._overrideMarkerIcon(layer);
        }

        layer.on(this._childMarkerEventHandlers, this);

        //Find the lowest zoom level to slot this one in
        for (; zoom >= minZoom; zoom--) {
            markerPoint = this._map.project(layer.getLatLng(), zoom); // calculate pixel position

            //Try find a cluster close by
            var closest = gridClusters[zoom].getNearObject(markerPoint);
            if (closest) {
                closest._addChild(layer);
                layer.__parent = closest;
                return;
            }

            //Try find a marker close by to form a new cluster with
            closest = gridUnclustered[zoom].getNearObject(markerPoint);
            if (closest) {
                var parent = closest.__parent;
                if (parent) {
                    this._removeLayer(closest, false);
                }

                //Create new cluster with these 2 in it

                var newCluster = new this._markerCluster(this, zoom, closest, layer);
                gridClusters[zoom].addObject(newCluster, this._map.project(newCluster._cLatLng, zoom));
                closest.__parent = newCluster;
                layer.__parent = newCluster;

                //First create any new intermediate parent clusters that don't exist
                var lastParent = newCluster;
                for (z = zoom - 1; z > parent._zoom; z--) {
                    lastParent = new this._markerCluster(this, z, lastParent);
                    gridClusters[z].addObject(lastParent, this._map.project(closest.getLatLng(), z));
                }
                parent._addChild(lastParent);

                //Remove closest from this zoom level and any above that it is in, replace with newCluster
                this._removeFromGridUnclustered(closest, zoom);

                return;
            }

            //Didn't manage to cluster in at this zoom, record us as a marker here and continue upwards
            gridUnclustered[zoom].addObject(layer, markerPoint);
        }

        //Didn't get in anything, add us to the top
        this._topClusterLevel._addChild(layer);
        layer.__parent = this._topClusterLevel;
        return;
    },

    /**
     * Refreshes the icon of all "dirty" visible clusters.
     * Non-visible "dirty" clusters will be updated when they are added to the map.
     * @private
     */
    _refreshClustersIcons: function () {
        this._featureGroup.eachLayer(function (c) {
            if (c instanceof L.MarkerCluster && c._iconNeedsUpdate) {
                c._updateIcon();
            }
        });
    },

    //Enqueue code to fire after the marker expand/contract has happened
    _enqueue: function (fn) {
        this._queue.push(fn);
        if (!this._queueTimeout) {
            this._queueTimeout = setTimeout(L.bind(this._processQueue, this), 300);
        }
    },
    _processQueue: function () {
        for (var i = 0; i < this._queue.length; i++) {
            this._queue[i].call(this);
        }
        this._queue.length = 0;
        clearTimeout(this._queueTimeout);
        this._queueTimeout = null;
    },

    //Merge and split any existing clusters that are too big or small
    _mergeSplitClusters: function () {
        var mapZoom = Math.round(this._map._zoom);

        //In case we are starting to split before the animation finished
        this._processQueue();

        if (this._zoom < mapZoom && this._currentShownBounds.intersects(this._getExpandedVisibleBounds())) { //Zoom in, split
            this._animationStart();
            //Remove clusters now off screen
            this._topClusterLevel._recursivelyRemoveChildrenFromMap(this._currentShownBounds, Math.floor(this._map.getMinZoom()), this._zoom, this._getExpandedVisibleBounds());

            this._animationZoomIn(this._zoom, mapZoom);

        } else if (this._zoom > mapZoom) { //Zoom out, merge
            this._animationStart();

            this._animationZoomOut(this._zoom, mapZoom);
        } else {
            this._moveEnd();
        }
    },

    //Gets the maps visible bounds expanded in each direction by the size of the screen (so the user cannot see an area we do not cover in one pan)
    _getExpandedVisibleBounds: function () {
        if (!this.options.removeOutsideVisibleBounds) {
            return this._mapBoundsInfinite;
        } else if (L.Browser.mobile) {
            return this._checkBoundsMaxLat(this._map.getBounds());
        }

        return this._checkBoundsMaxLat(this._map.getBounds().pad(1)); // Padding expands the bounds by its own dimensions but scaled with the given factor.
    },

    /**
     * Expands the latitude to Infinity (or -Infinity) if the input bounds reach the map projection maximum defined latitude
     * (in the case of Web/Spherical Mercator, it is 85.0511287798 / see https://en.wikipedia.org/wiki/Web_Mercator#Formulas).
     * Otherwise, the removeOutsideVisibleBounds option will remove markers beyond that limit, whereas the same markers without
     * this option (or outside MCG) will have their position floored (ceiled) by the projection and rendered at that limit,
     * making the user think that MCG "eats" them and never displays them again.
     * @param bounds L.LatLngBounds
     * @returns {L.LatLngBounds}
     * @private
     */
    _checkBoundsMaxLat: function (bounds) {
        var maxLat = this._maxLat;

        if (maxLat !== undefined) {
            if (bounds.getNorth() >= maxLat) {
                bounds._northEast.lat = Infinity;
            }
            if (bounds.getSouth() <= -maxLat) {
                bounds._southWest.lat = -Infinity;
            }
        }

        return bounds;
    },

    //Shared animation code
    _animationAddLayerNonAnimated: function (layer, newCluster) {
        if (newCluster === layer) {
            this._featureGroup.addLayer(layer);
        } else if (newCluster._childCount === 2) {
            newCluster._addToMap();

            var markers = newCluster.getAllChildMarkers();
            this._featureGroup.removeLayer(markers[0]);
            this._featureGroup.removeLayer(markers[1]);
        } else {
            newCluster._updateIcon();
        }
    },

    /**
     * Extracts individual (i.e. non-group) layers from a Layer Group.
     * @param group to extract layers from.
     * @param output {Array} in which to store the extracted layers.
     * @returns {*|Array}
     * @private
     */
    _extractNonGroupLayers: function (group, output) {
        var layers = group.getLayers(),
            i = 0,
            layer;

        output = output || [];

        for (; i < layers.length; i++) {
            layer = layers[i];

            if (layer instanceof L.LayerGroup) {
                this._extractNonGroupLayers(layer, output);
                continue;
            }

            output.push(layer);
        }

        return output;
    },

    /**
     * Implements the singleMarkerMode option.
     * @param layer Marker to re-style using the Clusters iconCreateFunction.
     * @returns {L.Icon} The newly created icon.
     * @private
     */
    _overrideMarkerIcon: function (layer) {
        var icon = layer.options.icon = this.options.iconCreateFunction({
            getChildCount: function () {
                return 1;
            },
            getAllChildMarkers: function () {
                return [layer];
            }
        });

        return icon;
    }
});

// Constant bounds used in case option "removeOutsideVisibleBounds" is set to false.
L.MarkerClusterGroup.include({
    _mapBoundsInfinite: new L.LatLngBounds(new L.LatLng(-Infinity, -Infinity), new L.LatLng(Infinity, Infinity))
});

L.MarkerClusterGroup.include({
    _noAnimation: {
        //Non Animated versions of everything
        _animationStart: function () {
            //Do nothing...
        },
        _animationZoomIn: function (previousZoomLevel, newZoomLevel) {
            this._topClusterLevel._recursivelyRemoveChildrenFromMap(this._currentShownBounds, Math.floor(this._map.getMinZoom()), previousZoomLevel);
            this._topClusterLevel._recursivelyAddChildrenToMap(null, newZoomLevel, this._getExpandedVisibleBounds());

            //We didn't actually animate, but we use this event to mean "clustering animations have finished"
            this.fire('animationend');
        },
        _animationZoomOut: function (previousZoomLevel, newZoomLevel) {
            this._topClusterLevel._recursivelyRemoveChildrenFromMap(this._currentShownBounds, Math.floor(this._map.getMinZoom()), previousZoomLevel);
            this._topClusterLevel._recursivelyAddChildrenToMap(null, newZoomLevel, this._getExpandedVisibleBounds());

            //We didn't actually animate, but we use this event to mean "clustering animations have finished"
            this.fire('animationend');
        },
        _animationAddLayer: function (layer, newCluster) {
            this._animationAddLayerNonAnimated(layer, newCluster);
        }
    },

    _withAnimation: {
        //Animated versions here
        _animationStart: function () {
            this._map._mapPane.className += ' leaflet-cluster-anim';
            this._inZoomAnimation++;
        },

        _animationZoomIn: function (previousZoomLevel, newZoomLevel) {
            var bounds = this._getExpandedVisibleBounds(),
                fg = this._featureGroup,
                minZoom = Math.floor(this._map.getMinZoom()),
                i;

            this._ignoreMove = true;

            //Add all children of current clusters to map and remove those clusters from map
            this._topClusterLevel._recursively(bounds, previousZoomLevel, minZoom, function (c) {
                var startPos = c._latlng,
                    markers = c._markers,
                    m;

                if (!bounds.contains(startPos)) {
                    startPos = null;
                }

                if (c._isSingleParent() && previousZoomLevel + 1 === newZoomLevel) { //Immediately add the new child and remove us
                    fg.removeLayer(c);
                    c._recursivelyAddChildrenToMap(null, newZoomLevel, bounds);
                } else {
                    //Fade out old cluster
                    c.clusterHide();
                    c._recursivelyAddChildrenToMap(startPos, newZoomLevel, bounds);
                }

                //Remove all markers that aren't visible any more
                //TODO: Do we actually need to do this on the higher levels too?
                for (i = markers.length - 1; i >= 0; i--) {
                    m = markers[i];
                    if (!bounds.contains(m._latlng)) {
                        fg.removeLayer(m);
                    }
                }

            });

            this._forceLayout();

            //Update opacities
            this._topClusterLevel._recursivelyBecomeVisible(bounds, newZoomLevel);
            //TODO Maybe? Update markers in _recursivelyBecomeVisible
            fg.eachLayer(function (n) {
                if (!(n instanceof L.MarkerCluster) && n._icon) {
                    n.clusterShow();
                }
            });

            //update the positions of the just added clusters/markers
            this._topClusterLevel._recursively(bounds, previousZoomLevel, newZoomLevel, function (c) {
                c._recursivelyRestoreChildPositions(newZoomLevel);
            });

            this._ignoreMove = false;

            //Remove the old clusters and close the zoom animation
            this._enqueue(function () {
                //update the positions of the just added clusters/markers
                this._topClusterLevel._recursively(bounds, previousZoomLevel, minZoom, function (c) {
                    fg.removeLayer(c);
                    c.clusterShow();
                });

                this._animationEnd();
            });
        },

        _animationZoomOut: function (previousZoomLevel, newZoomLevel) {
            this._animationZoomOutSingle(this._topClusterLevel, previousZoomLevel - 1, newZoomLevel);

            //Need to add markers for those that weren't on the map before but are now
            this._topClusterLevel._recursivelyAddChildrenToMap(null, newZoomLevel, this._getExpandedVisibleBounds());
            //Remove markers that were on the map before but won't be now
            this._topClusterLevel._recursivelyRemoveChildrenFromMap(this._currentShownBounds, Math.floor(this._map.getMinZoom()), previousZoomLevel, this._getExpandedVisibleBounds());
        },

        _animationAddLayer: function (layer, newCluster) {
            var me = this,
                fg = this._featureGroup;

            fg.addLayer(layer);
            if (newCluster !== layer) {
                if (newCluster._childCount > 2) { //Was already a cluster

                    newCluster._updateIcon();
                    this._forceLayout();
                    this._animationStart();

                    layer._setPos(this._map.latLngToLayerPoint(newCluster.getLatLng()));
                    layer.clusterHide();

                    this._enqueue(function () {
                        fg.removeLayer(layer);
                        layer.clusterShow();

                        me._animationEnd();
                    });

                } else { //Just became a cluster
                    this._forceLayout();

                    me._animationStart();
                    me._animationZoomOutSingle(newCluster, this._map.getMaxZoom(), this._zoom);
                }
            }
        }
    },

    // Private methods for animated versions.
    _animationZoomOutSingle: function (cluster, previousZoomLevel, newZoomLevel) {
        var bounds = this._getExpandedVisibleBounds(),
            minZoom = Math.floor(this._map.getMinZoom());

        //Animate all of the markers in the clusters to move to their cluster center point
        cluster._recursivelyAnimateChildrenInAndAddSelfToMap(bounds, minZoom, previousZoomLevel + 1, newZoomLevel);

        var me = this;

        //Update the opacity (If we immediately set it they won't animate)
        this._forceLayout();
        cluster._recursivelyBecomeVisible(bounds, newZoomLevel);

        //TODO: Maybe use the transition timing stuff to make this more reliable
        //When the animations are done, tidy up
        this._enqueue(function () {

            //This cluster stopped being a cluster before the timeout fired
            if (cluster._childCount === 1) {
                var m = cluster._markers[0];
                //If we were in a cluster animation at the time then the opacity and position of our child could be wrong now, so fix it
                this._ignoreMove = true;
                m.setLatLng(m.getLatLng());
                this._ignoreMove = false;
                if (m.clusterShow) {
                    m.clusterShow();
                }
            } else {
                cluster._recursively(bounds, newZoomLevel, minZoom, function (c) {
                    c._recursivelyRemoveChildrenFromMap(bounds, minZoom, previousZoomLevel + 1);
                });
            }
            me._animationEnd();
        });
    },

    _animationEnd: function () {
        if (this._map) {
            this._map._mapPane.className = this._map._mapPane.className.replace(' leaflet-cluster-anim', '');
        }
        this._inZoomAnimation--;
        this.fire('animationend');
    },

    //Force a browser layout of stuff in the map
    // Should apply the current opacity and location to all elements so we can update them again for an animation
    _forceLayout: function () {
        //In my testing this works, infact offsetWidth of any element seems to work.
        //Could loop all this._layers and do this for each _icon if it stops working

        L.Util.falseFn(document.body.offsetWidth);
    }
});

L.markerClusterGroup = function (options) {
    return new L.MarkerClusterGroup(options);
};
